package test4;

import java.util.Scanner;

public class Solution1 { // 哈希表 - 分离链法
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入哈希表大小：");
        int size = sc.nextInt();
        HashTable hashTable = new HashTable(size);
        while (true) {
            System.out.println("请选择要做的操作：");
            String choice = sc.next();
            switch (choice) {
                case "add":
                    System.out.println("请输入要存入数字的数量：");
                    int num = sc.nextInt();
                    System.out.println("请输入要存入的数字：");
                    for (int i = 0; i < num; i++) {
                        hashTable.addElem(sc.nextInt());
                    }
                    break;
                case "show":
                    hashTable.showHashTable();
                    break;
                case "delete":
                    System.out.println("请输入要删除的元素：");
                    int del = sc.nextInt();
                    hashTable.deleteElem(del);
                    break;
                case "find":
                    System.out.println("请输入要查询的元素：");
                    int fin = sc.nextInt();
                    hashTable.findElem(fin);
                    break;
                case "exit":
                    System.exit(0);
                    break;
            }
        }
    }
}

//哈希表
class HashTable{
    private LinkedList[] linkedListArray;

    private int size;//链表条数

    public HashTable(int size){
        this.size = size;
        linkedListArray = new LinkedList[size];
        //初始化每条链表
        for (int i = 0; i < size; i++) {
            linkedListArray[i] = new LinkedList();
        }
    }

    //添加链表
    public void addElem(int elem){
        int pos = hashFunc(elem);
        linkedListArray[pos].add(elem);
    }

    //散列函数
    public int hashFunc(int elem){
        return  elem % size;
    }

    public void showHashTable(){
        for (int i = 0; i < size; i++){
            linkedListArray[i].showList(i);
            System.out.println();
        }
    }

    public void deleteElem(int elem){
        int pos = hashFunc(elem);
        linkedListArray[pos].delete(elem);
    }

    public void findElem(int elem){
        int pos = hashFunc(elem);
        linkedListArray[pos].find(elem, pos);
    }
}

//链表
class LinkedList{
    private Node head;

    public LinkedList(){}

    public void add(int elem){
        if (head == null){
            head = new Node();
            head.data = elem;
        }else {
            //临时结点，用于定位到最后结点
            Node p = head;
            while (p.next != null){//将p移向最后结点
                p = p.next;
            }
            p.next = new Node();
            p.next.data = elem;
        }
    }

    public void showList(int no){
        if (head == null){
            System.out.print("链表" + no + "为空");
        }else {
            Node p = head;
            while (p != null){
                if (p.next != null){
                    System.out.print(p.data + "->");
                }else {
                    System.out.print(p.data);
                }
                p = p.next;
            }
        }
    }

    public void delete(int elem){
        if (head == null){
            System.out.println("该链表为空，请重新输入！");
        }else {
            Node p = head;
            if (head.data == elem){//要删除的元素在头结点
                head = head.next;
                return;
            }
            while (p.next != null && p.next.data != elem){
                p = p.next;
            }
            if (p.next == null && p.data == elem){//如果要删除的结点为最后一个节点
                p = null;
            } else if (p.next == null){//没有找到要删除的元素
                System.out.println("找不到要删除的元素，请重新输入！");
            } else { //要删除的结点为中间结点
                p.next = p.next.next;
            }
        }
    }

    public void find(int elem, int pos){
        if (head == null){
            System.out.println("找不到该元素");
        }else {
            Node p = head;
            int count = 1;
            if (head.data == elem){
                System.out.println("该元素首次出现在" + pos + "号链表,第1个位置");
                return;
            }
            while (p.next != null && p.data != elem){//找到符合条件的元素或者p指向末尾
                p = p.next;
                count++;
            }
            if (p.data == elem){
                System.out.println("该元素首次出现在" + pos + "号链表,第" + count + "个位置");
           } else {
                System.out.println("找不到该元素");
            }
        }
    }
}

//结点
class Node{
    int data;
    Node next;
    public Node(){}
}
